#pragma once
#include <iostream>
#include <vector>

using namespace std;
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return (size_t)key;
    }
};

template <>
struct HashFunc<string>
{
    size_t operator()(const string& s)
    {
        size_t hashi = 0;
        for(auto e : s)
        {
            hashi *= 31;
            hashi += e;
        }
        return hashi;
    }
};

namespace ltw
{
    template<class T>
    struct HashNode
    {
        T _data;
        HashNode<T>* _next;
        HashNode(const T& data)
            :_data(data)
            ,_next(nullptr)
        {

        }
    };


    //前置声明
    template<class K,class T,class KeyOfT,class Hash>
    class HashTable;


    template<class K,class T,class Ptr,class Ref,class KeyOfT,class Hash>
    struct HTIterator
    {
        typedef HashNode<T> Node;
        typedef HTIterator<K,T,Ptr,Ref,KeyOfT,Hash> Self;

        Node* _node;
        const HashTable<K,T,KeyOfT,Hash>* _pht;
        HTIterator(Node* node,const HashTable<K,T,KeyOfT,Hash>* pht)
            :_node(node)
            ,_pht(pht)
        {

        }

        Ref operator*()
        {
            return _node->_data;
        }

        Ptr operator->()
        {
            return &_node->_data;
        }

        bool operator!=(const Self& s)
        {
            return _node != s._node;
        }

        Self& operator++()
        {
            if(_node->_next)
            {
                //当前桶还要节点
                _node = _node->_next;
            }
            else
            {
                //当前桶没节点了,找下一个不为空桶
                KeyOfT kot;
                Hash hs;
                size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
                ++hashi;
                while(hashi < _pht->_tables.size())
                {
                    if(_pht->_tables[hashi])
                    {
                        break;
                    }
                    ++hashi;
                }

                if(hashi == _pht->_tables.size())
                {
                    _node = nullptr; //end()
                }
                else
                {
                    _node = _pht->_tables[hashi];
                }
            }
            return *this;
        }
    };

    //  1、实现哈希表
	//  2、封装unordered_map和unordered_set  解决KeyOfT
	//  3、iterator
	//  4、const_iterator
	//  5、修改key的问题
	//  6、operator[]

    template<class K,class T,class KeyOfT,class Hash>
    class HashTable
    {
        //友元声明
        template<class K_,class T_,class Ptr,class Ref,class KeyOfT_,class Hash_>
        friend struct HTIterator;

        typedef HashNode<T> Node;
    public:
        typedef HTIterator<K,T,T*,T&,KeyOfT,Hash> Iterator;
        typedef HTIterator<K,T,const T*,const T&,KeyOfT,Hash> Const_Iterator;

        Iterator Begin()
        {
            if(_n == 0)
            {
                return End();
            }
            for(size_t i = 0;i < _tables.size();i++)
            {
                Node* cur = _tables[i];
                if(cur)
                {
                    return Iterator(cur,this);
                }
            }
            return End();
        }

        Iterator End()
        {
            return Iterator(nullptr,this);
        }

        Const_Iterator Begin()const
        {
            if(_n == 0)
            {
                return End();
            }
            for(size_t i = 0;i < _tables.size();i++)
            {
                Node* cur = _tables[i];
                if(cur)
                {
                    return Const_Iterator(cur,this);
                }
            }
            return End();
        }

        Const_Iterator End()const
        {
            return Const_Iterator(nullptr,this);
        }


        HashTable()
        {
            _tables.resize(10,nullptr);
        }
        ~HashTable()
        {
            //只要把我们的_tables下的链表释放掉
            for(size_t i = 0;i < _tables.size();i++)
            {
                Node* cur = _tables[i];
                while(cur)
                {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
        }

        pair<Iterator,bool> Insert(const T& data)
        {
            KeyOfT kot;
            Iterator it = Find(kot(data));
            if(it != End())
            {
                return {it,false};
            }

            Hash hs;
            size_t hashi = hs(kot(data)) % _tables.size();

            // 负载因子==1  -->  扩容
            if(_n == _tables.size())
            {
                vector<Node*> newtables(_tables.size() * 2,nullptr);
                for(size_t i = 0;i < _tables.size();i++)
                {
                    Node* cur = _tables[i];
                    while(cur)
                    {
                        Node* next = cur->_next;
                        //旧表中的节点,挪动到新表的重新映射的位置
                        size_t hashi = hs(kot(cur->_data)) % newtables.size();
                        // 头插到新表
                        cur->_next = newtables[hashi];
                        newtables[hashi] = cur;
                        cur = next;
                    }
                    _tables[i] = nullptr;
                }
                _tables.swap(newtables);
            }

            //头插
            Node* newnode = new Node(data);
            newnode->_next = _tables[hashi];
            _tables[hashi] = newnode;
            ++_n;
            return {Iterator(newnode,this),true};
        }

        Iterator Find(const K& key)
        {
            KeyOfT kot;
            Hash hs;
            size_t hashi = hs(key) % _tables.size();
            Node* cur = _tables[hashi];
            while(cur)
            {
                if(kot(cur->_data) == key)
                {
                    return Iterator(cur,this);
                }
                cur = cur->_next;
            }
            return End();
        }

        bool Erase(const K& key)
        {
            KeyOfT kot;
            Hash hs;
            size_t hashi = hs(key) % _tables.size();
            Node* prev = nullptr;
            Node* cur = _tables[hashi];
            while(cur)
            {
                if(kot(cur->_data) == key)
                {
                    if(prev == nullptr)
                    {
                        _tables[hashi] = cur->_next;
                    }
                    else
                    {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    --_n;
                    return true;
                }
                prev = cur;
                cur = cur->_next;
            }
            return false;
        }

    private:
        vector<Node*> _tables;
        size_t _n = 0; //表中存储数据个数
    };
}
